1. Field of the Invention
The invention relates generally to electronic transformation of an image into a modified image which has undergone expansion, contraction, folding, rippling, curling, twisting or other modification or distortion, or a combination thereof. Typically, a two-dimensional image may be subjected to a three-dimensional effect, such as being folded over upon itself, and then displayed as a modified two-dimensional image. As will be apparent, in presenting a folded image, provision must be made for deleting the portions falling in back of other sections of the image. Folding and other effects result in image transformation problems which have been complex, expensive or impossible to provide for on a practical basis in the prior art.
Image warping is a geometric transformation that redefines the spatial relationship between points in an image. This area has received considerable attention due to its practical importance in remote sensing, medical imaging, computer vision, and computer graphics. Typical applications include distortion compensation of imaging sensors, decalibration for image registration, geometrical normalization for image analysis and display, map projection, and texture mapping for image synthesis.
2. Description of the Prior Art
Image warping has benefited dramatically from developments in separable geometric transformation algorithms. Also known as scanline algorithms, these methods reduce a two-dimensional ("2-D") resampling problem into a sequence of one-dimensional ("1-D") scanline resampling operations. This makes them amenable to streamline processing and allows them to be implemented with conventional hardware. Scanline algorithms have been shown to apply over a wide range of transformations, including perspective projection of rectangles, bivariate patches, and superquadrics. Hardware products such as the Quantel Mirage system, the Ampex system as described in U.S. Pat. Nos. 4,463,372, 4,468,688 and 4,472,732, and the Honeywell system as described in U.S. Pat. No. 4,835,532, are based on these techniques in order to produce real-time video effects for television and other applications.
Early ideas on scanline algorithms are presented in a paper by Catmull and Smith, "3-D Transformations of Images in Scanline Order", Computer Graphics (SIGGRAPH '80 Proceedings), vol. 14, no. 3, pp. 279-285, July 1980. It describes a two-pass technique that decomposes the 2-D resampling problem into two orthogonal 1-D resampling stages. This is the basis for much of the other separable work. Nevertheless, the approach suffers from problems known as "bottleneck" and "foldover"--difficulties which can result in visual artifacts and costly memory requirements.